10065 - Useless tile packers/10065.2.cpp

   1 #include <iostream>
   2 #include <vector>
   3 #include <algorithm>
   4 #include <iterator>
   5 #include <cmath>
   6
   7 using namespace std;
   8
   9 struct point{
  10   int x,y;
  11   point() {}
  12   point(int X, int Y) : x(X), y(Y) {}
  13 };
  14
  15 point pivot;
  16
  17 ostream& operator<< (ostream& out, const point& c)
  18 {
  19   out << "(" << c.x << "," << c.y << ")";
  20   return out;
  21 }
  22
  23 //P es un polígono ordenado anticlockwise.
  24 //Si es clockwise, retorna el area negativa.
  25 //Si no esta ordenado retorna pura mierda
  26 double area(const vector<point> &p){
  27   double r = 0.0;
  28   for (int i=0; i<p.size(); ++i){
  29     int j = (i+1) % p.size();
  30     r += p[i].x*p[j].y - p[j].x*p[i].y;
  31   }
  32   return r/2.0;
  33 }
  34
  35 //retorna si c esta a la izquierda de el segmento AB
  36 inline int cross(const point &a, const point &b, const point &c){
  37   return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
  38 }
  39
  40 //Self < that si esta a la derecha del segmento Pivot-That
  41 bool angleCmp(const point &self, const point &that){
  42   return( cross(pivot, that, self) < 0 );
  43 }
  44
  45 inline int distsqr(const point &a, const point &b){
  46   return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
  47 }
  48
  49 //vector p tiene los puntos ordenados anticlockwise
  50 vector<point> graham(vector<point> p){
  51   pivot = p[0];
  52   sort(p.begin(), p.end(), angleCmp);
  53   //Ordenar por ángulo y eliminar repetidos.
  54   //Si varios puntos tienen el mismo angulo se borran todos excepto el que esté más lejos
  55   for (int i=1; i<p.size()-1; ++i){
  56     if (cross(p[0], p[i], p[i+1]) == 0){ //Si son colineales...
  57       if (distsqr(p[0], p[i]) < distsqr(p[0], p[i+1])){ //Borrar el mas cercano
  58         p.erase(p.begin() + i);
  59       }else{
  60         p.erase(p.begin() + i + 1);
  61       }
  62       i--;
  63     }
  64   }
  65
  66   vector<point> chull(p.begin(), p.begin()+3);
  67
  68   //Ahora sí!!!
  69   for (int i=3; i<p.size(); ++i){
  70     while ( chull.size() >= 2 && cross(chull[chull.size()-2], chull[chull.size()-1], p[i]) < 0){
  71       chull.erase(chull.end() - 1);
  72     }
  73     chull.push_back(p[i]);
  74   }
  75
  76   return chull;
  77 }
  78
  79 int main(){
  80   int n;
  81   int tileNo = 1;
  82   while (cin >> n && n){
  83     vector<point> p;
  84     point min(10000, 10000);
  85     int minPos;
  86     for (int i=0; i<n; ++i){
  87       int x, y;
  88       cin >> x >> y;
  89       p.push_back(point(x,y));
  90       if (y < min.y || (y == min.y && x < min.x )){
  91         min = point(x,y);
  92         minPos = i;
  93       }
  94     }
  95     double tileArea = fabs(area(p));
  96
  97     //Destruye el orden cw|ccw poligono, pero hay que hacerlo por que Graham necesita el pivote en p[0]
  98     swap(p[0], p[minPos]);
  99     pivot = p[0];
 100     double chullArea = fabs(area(graham(p)));
 101
 102     printf("Tile #%d\n", tileNo++);
 103     printf("Wasted Space = %.2f \%\n\n",  (chullArea - tileArea) * 100.0 / chullArea);
 104
 105   }
 106   return 0;
 107 }